package example;

import java.util.Arrays;
import java.util.Random;

/**
 * 递归， 分治， 贪心， 回溯， 动态规划
 *
 * 递归的微观解读, 添加打印输出, 观察递归过程, 深入理解递归的执行
 * > 定义好循环不变量, 遍历过程整理数组, 整理过程中始终维持循环不变量
 * > 小规模的数据量, 插入排序有时候比快速排序更快一些. 小范围的排序可以使用插入排序进行代码优化.  -- 多小这个量就是算法中的优化参数
 *
 * > 普通算法 -> 看最差情况的复杂度
 * > 随机算法 -> 看期望的复杂度
 * > 算法参数 -> 插入排序优化的边界量
 */
public class Quick {

    private Quick() {}

    public static <E extends Comparable<E>> void sort(E[] data, int l, int r) {
        if (l >= r) return;  // 基本问题
        int p = partition(data, l ,r, Utils.rnd());
        sort(data, l, p - 1);
        sort(data, p + 1, r);
    }

    // [l + 1, j - 1] <= data[pivot]   [j, i) > data[pivot],   i == r + 1 时循环结束
    public static <E extends Comparable<E>> int partition(E[] data, int l, int r, Random rnd) {
        Utils.swap(data, l, rnd.nextInt(r - l + 1) + l);
        int j = l + 1;
        for (int i = l + 1; i <= r; i++) {
            if (data[i].compareTo(data[l]) <= 0)
                Utils.swap(data, i, j++);
        }
        Utils.swap(data, l, j - 1);
        return j - 1;
    }

    // 双路快速排序 -> 可以对任意数据样例进行排序， 不会因为有序样本和重复元素样本导致退化 《快速排序是随机算法》
    public static <E extends Comparable<E>> void sort2Ways(E[] data) {
        sort2Ways(data, 0, data.length - 1);
    }

    private static <E extends Comparable<E>> void sort2Ways(E[] data, int l, int r) {
        if (l >= r) return;
        int p = partition2Ways(data, l, r, Utils.rnd());
        sort2Ways(data, l, p - 1);
        sort2Ways(data, p + 1, r);
    }

    // 循环不变量 [l+1, i - 1] <= v, [j + 1, r] >= v,  i = l + 1, j = r
    private static <E extends Comparable<E>> int partition2Ways(E[] data, int l, int r, Random rnd) {
        Utils.swap(data, l, rnd.nextInt(r - l + 1) + l);
        int i = l + 1, j = r;
        while (true) {
            while (i <= j && data[i].compareTo(data[l]) < 0) i++;
            while (i <= j && data[j].compareTo(data[l]) > 0) j--;
            if (i > j) break;
            Utils.swap(data, i, j);
            i++; j--;
        }
        Utils.swap(data, l, j);
        return j;
    }


    // 三路快速排序 -> 特定数据样例情况下， 三路快速排序的复杂度是O(n)
    public static <E extends Comparable<E>> void sort3Ways(E[] data) {
        sort2Ways(data, 0, data.length - 1);
    }

    private static <E extends Comparable<E>> void sort3Ways(E[] data, int l, int r) {
        if (l >= r) return;
        Bound b = partition3Ways(data, l, r, Utils.rnd());
        sort3Ways(data, l, b.lt);
        sort3Ways(data, b.gt, r);
    }

    // 循环不变量 [l + 1, lt] < v,  [lt + 1, i - 1] = v, [gt, r] > v
    private static <E extends Comparable<E>> Bound partition3Ways(E[] data, int l, int r, Random rnd) {
        // 添加随机化 <= 快速排序是个随机算法
        // 随机选择一个位置的元素交换到 l 位置
        Utils.swap(data, l, rnd.nextInt(r - l + 1) + l);
        // pivot = l 标定点
        int lt = l, i = l + 1, gt = r + 1;
        while(i < gt) {
            if (data[i].compareTo(data[l]) < 0)
                Utils.swap(data, i++, ++lt);
            else if (data[i].compareTo(data[l]) > 0)
                Utils.swap(data, i, --gt);
            else i++;
        }
        Utils.swap(data, lt, l);
        return new Bound(lt - 1, gt);
    }

    static class Bound {
        public int lt;
        public int gt;
        public Bound(int lt, int gt) {
            this.lt = lt;
            this.gt = gt;
        }
    }

    public static void main(String[] args) {
//        Integer[] data = Utils.randomArray(10000, 10000);
//        Utils.timeSpent(Quick::sort3Ways, "三路快速排序", data, 0, data.length - 1);


        for (int n : new int[]{100_0000, 1000_0000}) {
            Integer[] data = Utils.randomArray(n, n);
            Integer[] dup = Arrays.copyOf(data, data.length);
            Integer[] dupp = Arrays.copyOf(data, data.length);
            System.out.println("随机数据样例：");
            Utils.timeSpent(Quick::sort, " > 单路快速排序 >", data, 0, data.length - 1);
            Utils.timeSpent(Quick::sort2Ways, " > 双路快速排序 >", dup, 0, dup.length - 1);
            Utils.timeSpent(Quick::sort3Ways, " > 三路快速排序 >", dupp, 0, dupp.length - 1);

            Integer[] data2 = Utils.orderedArray(n);
            Integer[] dup2 = Arrays.copyOf(data2, data2.length);
            Integer[] dup22 = Arrays.copyOf(data2, data2.length);
            System.out.println("顺序数据样例：");
            Utils.timeSpent(Quick::sort, " > 单路快速排序 >", data2, 0, data2.length - 1);
            Utils.timeSpent(Quick::sort2Ways, " > 双路快速排序 >", dup2, 0, dup2.length - 1);
            Utils.timeSpent(Quick::sort3Ways, " > 三路快速排序 >", dup22, 0, dup22.length - 1);

            Integer[] data3 = Utils.orderedArray(n);
            Integer[] dup3 = Arrays.copyOf(data3, data3.length);
            Integer[] dup33 = Arrays.copyOf(data3, data3.length);
            System.out.println("重复数据样例：");
            Utils.timeSpent(Quick::sort, " > 单路快速排序 >", data3, 0, data3.length - 1);
            Utils.timeSpent(Quick::sort2Ways, " > 双路快速排序 >", dup3, 0, dup3.length - 1);
            Utils.timeSpent(Quick::sort3Ways, " > 三路快速排序 >", dup33, 0, dup33.length - 1);
        }
    }
}


